package hot;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

public class ersanjiu {
//    https://leetcode.cn/problems/sliding-window-maximum/submissions/679573713/?envType=study-plan-v2&envId=top-100-liked
//class Solution {
//    public int[] maxSlidingWindow(int[] nums, int k) {
//        int n = nums.length;
//        int[] ans = new int[n - k + 1]; // 窗口个数
//        Deque<Integer> q = new ArrayDeque<>(); // 更快的写法见【Java 数组】
//
//        for (int i = 0; i < n; i++) {
//            // 1. 右边入
//            while (!q.isEmpty() && nums[q.getLast()] <= nums[i]) {
//                q.removeLast(); // 维护 q 的单调性
//            }
//            q.addLast(i); // 注意保存的是下标，这样下面可以判断队首是否离开窗口
//
//            // 2. 左边出
//            int left = i - k + 1; // 窗口左端点
//            if (q.getFirst() < left) { // 队首离开窗口
//                q.removeFirst();
//            }
//
//            // 3. 在窗口左端点处记录答案
//            if (left >= 0) {
//                // 由于队首到队尾单调递减，所以窗口最大值就在队首
//                ans[left] = nums[q.getFirst()];
//            }
//        }
//
//        return ans;
//    }
//}

    public static int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length == 0 || k == 0) return new int[0];
        Deque<Integer> deque = new LinkedList<>();
        int[] res = new int[nums.length - k + 1];
        for(int j = 0, i = 1 - k; j < nums.length; i++, j++) {
            // 删除 deque 中对应的 nums[i-1]
            if(i > 0 && deque.peekFirst() == nums[i - 1])
                deque.removeFirst();
            // 保持 deque 递减
            while(!deque.isEmpty() && deque.peekLast() < nums[j])
                deque.removeLast();
            deque.addLast(nums[j]);
            // 记录窗口最大值
            if(i >= 0)
                res[i] = deque.peekFirst();
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums={1,3,-1,-3,5,3,6,7};
        int[] ints = maxSlidingWindow(nums, 3);
        System.out.println(Arrays.toString(nums));


    }
}



